#ifndef HEAP_FUNCTIONS
#define HEAP_FUNCTIONS

#include <vector>
#include <functional>

using namespace std;

// the vector elements in the range [0, last-1) are a heap.
// insert the element v[last-1] into the heap so that the
// range [0, last) is a heap. use the function object comp
// to perform comparisons
template <typename T, typename Compare>
void pushHeap(vector<T>& v, int last, Compare comp);

// filter the vector element v[first] down the heap with index
// range [first, last)
template <typename T, typename Compare>
void adjustHeap(vector<T>& v, int first, int last, Compare comp);

// the vector elements in the range [0, last) are a heap.
// swap the first and last elements of the heap and then
// make the elements in the index range [0, last-1) a heap.
// use the function object comp to perform comparisons
template <typename T, typename Compare>
void popHeap(vector<T>& v, int last, Compare comp);

// arrange the vector elements into a heap. use the function
// object comp to perform comparisons
template <typename T, typename Compare>
void makeHeap(vector<T>& v, Compare comp);

// implementations

template <typename T, typename Compare>
void pushHeap(vector<T>& v, int last, Compare comp)
{
    // assume the new item is at location v[last-1] and that
    // the elements v[0] to v[last-2] are in heap order
    int currentPos, parentPos;
    T target;

    // currentPos is an index that traverses path of parents.
    // target is value hlist[i] and is repositioned in path
    currentPos = last-1;
    parentPos = (currentPos-1)/2;
    target = v[last-1];

    // traverse path of parents up to the root
    while (currentPos != 0)
    {
        // compare target and parent value
        if (comp(v[parentPos],target))
        {
            // move data from parent position to current
            // position. update current position to parent
            // position. compute next parent
            v[currentPos] = v[parentPos];
            currentPos = parentPos;
            parentPos = (currentPos-1)/2;
        }
        else
            // if !comp(parentvalue, target), heap condition is ok. break
            break;
    }
    // the correct location has been discovered. assign target
    v[currentPos] = target;
}


template <typename T, typename Compare>
void adjustHeap(vector<T>& v, int first, int last, Compare comp)
{
    int currentPos, childPos;
    T target;

    // start at first and filter target down the heap
    currentPos = first;
    target = v[first];

    // compute the left child index and begin a scan down
    // path of children, stopping at end of list (last)
    // or when we find a place for target
    childPos = 2 * currentPos + 1;
    while (childPos <= last-1)
    {
        // index of right child is childPos+1. compare the
        // two children. change childPos if
        // comp(v[childPos+1], v[childPos]) is true
        if ((childPos+1 <= last-1) &&
                comp(v[childPos], v[childPos+1]))
            childPos = childPos + 1;

        // compare selected child to target
        if (comp(target,v[childPos]))
        {
            // comp(selected child, target) is true.
            // move selected child to the parent;
            // position of selected child is now vacated
            v[currentPos] = v[childPos];

            // update indices to continue the scan
            currentPos = childPos;
            childPos = 2 * currentPos + 1;
        }
        else
            // target belongs at currentPos
            break;
    }
    v[currentPos] = target;
}

template <typename T, typename Compare>
void popHeap(vector<T>& v, int last, Compare comp)
{
    T temp;

    // exchange the first and last element in the heap
    temp = v[0];
    v[0] = v[last-1];
    v[last-1] = temp;

    // filter down the root over the range [0, last-1)
    adjustHeap(v, 0, last-1, comp);
}

template <typename T, typename Compare>
void makeHeap(vector<T>& v, Compare comp)
{
    int heapPos, lastPos;

    // compute the size of teh heap and the index
    // of the last parent
    lastPos = v.size();
    heapPos = (lastPos - 2)/2;

    // filter down every parent in order from last parent
    // down to root
    while (heapPos >= 0)
    {
        adjustHeap(v,heapPos, lastPos, comp);
        heapPos--;
    }
}

#endif	// HEAP_FUNCTIONS
